package org.labuladong.滑动窗口;

import java.util.HashMap;
import java.util.Map;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-0:47
 * @Description:
 * 给你⼀个字符串 s 、⼀个字符串 t，返回 s 中涵盖 t 所有字符的最⼩⼦串；如果 s 中不存在涵盖 t 所有字符
 * 的⼦串，则返回空字符串 ""。
 *
 * 标签：滑动窗⼝，数组双指针
 * @version: 1.0
 */
public class LC76_最小覆盖子串_AI_OK {

	/* 滑动窗⼝算法框架 */
	/**
	 * @Auther: qingle
	 * @Date: 2024/10/25-1:17
	 * @Description:
	 *
	 * 初始化：检查输入字符串是否有效，创建need哈希表存储目标字符串t中每个字符的出现次数。
	 * 滑动窗口：使用两个指针left和right表示窗口的左右边界。
	 * 扩展窗口：移动right指针扩展窗口，更新窗口内字符的计数。
	 * 更新有效字符计数：如果窗口中的字符计数满足need中的条件，则valid加一。
	 * 收缩窗口：当窗口包含了t中的所有字符时，尝试通过移动left指针来收缩窗口，并更新有效字符计数。
	 * 更新最小窗口：在每次可能收缩窗口时，检查当前窗口的长度是否小于之前记录的最小长度，并更新最小窗口的起始位置和长度。
	 * 返回结果：如果找到了满足条件的最小覆盖子串，则返回这个子串；否则返回空字符串。
	 *
	 * 这个简化后的模板依然保持了滑动窗口算法的核心逻辑，适用于解决最小窗口子串问题。
	 *
	 * @version: 1.0
	 */
	public static class model {
		public static String minWindow(String s, String t) {
			// 初始化需要的字符和窗口中的字符的哈希表
			Map<Character, Integer> need = new HashMap<>();
			Map<Character, Integer> window = new HashMap<>();
			for (char c : t.toCharArray()) {
				need.put(c, need.getOrDefault(c, 0) + 1);
			}

			int left = 0, right = 0;
			int valid = 0; // 窗口中满足条件的字符数量
			int start = 0; // 最小覆盖子串的起始索引
			int len = Integer.MAX_VALUE; // 最小覆盖子串的长度

			while (right < s.length()) {
				// 将移入窗口的字符c加入窗口
				char c = s.charAt(right);
				right++;

				// 如果c是t中的字符，则更新窗口计数
				if (need.containsKey(c)) {
					window.put(c, window.getOrDefault(c, 0) + 1);
					if (window.get(c).equals(need.get(c))) {
						valid++;
					}
				}

				// 当窗口包含了t的所有字符
				while (valid == need.size()) {
					// 更新最小覆盖子串
					if (right - left < len) {
						start = left;
						len = right - left;
					}

					// 将移出窗口的字符d从窗口中移除
					char d = s.charAt(left);
					left++;

					// 如果d是t中的字符，则更新窗口计数
					if (need.containsKey(d)) {
						if (window.get(d).equals(need.get(d))) {
							valid--;
						}
						window.put(d, window.get(d) - 1);
					}
				}
			}

			// 返回最小覆盖子串
			return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
		}

		public static void main(String[] args) {
			String s = "ADOBECODEBANC";
			String t = "ABC";
			System.out.println("Minimum window substring: " + model.minWindow(s, t)); // 应输出 "BANC"
		}
	}

}